package 五排序;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/22 15:09
 * 基数排序（桶排序）
 */
public class RadixSort {
    public static void main(String[] args) {

        int i = 10;
        int[] array = new int[i];
        //生成随机排序
        for (int k = 0; k < 10; k++) {

            for (int j = 0; j < i; j++) {
                array[j] = (int) (Math.random() * i * 1000);
            }

            //原本数组：
            System.out.printf("第%d \t次数组=》   ", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }

            //开始排序
            radixSort(array);

            //输出
            System.out.printf("，排序后为=》   ", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }
            System.out.println();
        }

    }

    public static void radixSort(int[] array) {
        //首先找到最大值，用来确定循环查找几次
        int maxNum = array[0];
        for (int i = 1; i < array.length; i++) {
            if (maxNum < array[i])
                maxNum = array[i];
        }
        //得到这个最大值有几位
        int maxLength = (maxNum + "").length();


        //n用来控制每次循环的时候取的位数
        for (int i = 1, n = 1; i <= maxLength; i++, n *= 10) {

            //定义一个二维数组来当桶
            int[][] bucket = new int[10][array.length];
            //定义一维数组来存放他的桶里面的元素个数
            int[] bucketElementCounts = new int[10];


            for (int j = 0; j < array.length; j++) {
                //分别取出每个位数上的数字
                int num = array[j] / n % 10;
                //bucket[几位数的桶][记录桶里面元素个数的数组[第几个数字]++]
                bucket[num][bucketElementCounts[num]++] = array[j];
            }

            //循环放入数据完成后把桶里的数据再次放入桶内  index用来控制哪个数字的桶
            int index = 0;
            //开始放入  j是代表第几个数字的桶
            for (int j = 0; j < 10; j++) {
                //读取桶内数据并保存
                for (int k = 0; k < bucketElementCounts[j]; k++) {
                    array[index++] = bucket[j][k];
                }
            }

            //重置每个桶记录
            bucketElementCounts = new int[10];
        }
    }
}
